package ren.wxyz.algorithm.fifteenalgorithm;

/**
 * 合并两个单链表，单链表是有序的
 * @author zxwang
 * @dateTime 2014年12月25日 下午5:28:20
 */
public class A02_MergeSingleChainTable {
	/**
	 * 禁止外部被初始化
	 */
	private A02_MergeSingleChainTable() {}
	
	/**
	 * 主方法
	 * @param args 命令行参数
	 */
	public static void main(String[] args) {
		
	}
	
	/**
	 * 合并单链表，没有头的链表
	 * @param n1 第一个链表
	 * @param n2 第二个链表
	 * @return 合并后的链表
	 */
	public static NodeL mergeSingleChainTable(NodeL n1, NodeL n2) {
		NodeL resNode = new NodeL();
		if (null == n1 && null != n2) {
			return n2;
		}
		else if (null != n1 && null == n2) {
			return n1;
		}
		else if (null == n1 && null == n2) {
			return null;
		}
		
		// 临时指向结果末尾节点
		NodeL n = resNode;
		
		// 遍历链表
		while (n1.getNext() != null && n2.getNext() != null) {
			if (n1.getValue() < n2.getValue()) {
				n.setNext(n1);
				n1 = n1.getNext();
			}
			else {
				n.setNext(n2);
				n2 = n2.getNext();
			}
			
			n = n.getNext();
		}
		
		return resNode.getNext();
	}
}
